UVa/673 - Parentheses balance/673.cpp

   1 #include <string>
   2 #include <iostream>
   3
   4 using namespace std;
   5
   6 bool valid(const string s){
   7   //cout << s << endl;
   8   if (s == "") return true;
   9
  10   int p=0, b=0, i;
  11   for (i = 0; i<s.size(); ++i){
  12     if (s[i] == '(') ++p;
  13     if (s[i] == ')') --p;
  14     if (s[i] == '[') ++b;
  15     if (s[i] == ']') --b;
  16
  17     if (p == 0 && b == 0){
  18       break;
  19     }
  20
  21   }
  22
  23   if (i < s.size()-1){
  24     return (valid(s.substr(0, i+1)) && valid(s.substr(i+1)));
  25   }
  26
  27   char first = s[0];
  28   char last = s[s.size() - 1];
  29   if ( (first == '(' && last == ')') || (first == '[' && last == ']') ){
  30     return (valid(s.substr(1, s.size()-2)));
  31   }
  32   return false;
  33 }
  34
  35 int main(){
  36   int n;
  37   cin >> n;
  38   while (getchar() != '\n');
  39   string s;
  40   while (n--){
  41     getline(cin, s);
  42     cout << (valid(s)?"Yes":"No") << endl;
  43   }
  44   return 0;
  45 }